/*
 * @Description: 归并排序算法实现
 * @Version: 
 * @Author: Weixin Zhu
 * @Date: 2020-12-09 13:45:31
 * @LastEditors: Weixin Zhu
 * @LastEditTime: 2020-12-11 16:47:39
 */
package com.zwx.algorithms.basic;

import com.zwx.algorithms.constant.AlgorithmsConstant;
import com.zwx.algorithms.pub.util.AlgorithmsUtils;
import com.zwx.algorithms.pub.util.LogUtils;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import cn.hutool.core.date.DateUtil;
import cn.hutool.core.date.StopWatch;

public class MergeSort extends AbstractArraySort {
    static final Logger log = LoggerFactory.getLogger(MergeSort.class);

    /**
     * @description: 归并排序算法实现
     * @param {Integer[]}
     *                        list
     * @param {int}
     *                        p,待排序集合的第p个元素，非数组下标, p<=q
     * @param {int}
     *                        q,待排序集合的第q个元素，非数组下标, q<=r
     * @param {int}
     *                        r,待排序集合的第r个元素，非数组下标, p<=q<=r
     * @return {*}
     */
    public void merge(Integer[] array, int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;
        totalStep++;
        if (AlgorithmsUtils.needShowStep(array.length)) {
            log.debug("index:{}, p:{}, q:{}, r:{},     n1:{}, n2:{}", totalStep, p, q, r, n1, n2);
        }
        if (AlgorithmsUtils.needShowStep(array.length)) {
            log.debug("--------merge-{}, array:{}", 1, array);
        }
        Integer[] l_array = new Integer[n1 + 1];
        Integer[] r_array = new Integer[n2 + 1];
        for (int i = 0; i < n1; i++) {
            l_array[i] = array[p + i - 1];
        }
        for (int j = 0; j < n2; j++) {
            r_array[j] = array[q + j];
        }
        int i = 0;
        int j = 0;

        for (int k = p - 1; k < r; k++) {
            totalStep++;
            if (l_array[i] == null) {
                array[k] = r_array[j];
                j = j + 1;
                continue;
            }

            if (r_array[j] == null) {
                array[k] = l_array[i];
                i = i + 1;
                continue;
            }

            if (l_array[i] <= r_array[j]) {
                array[k] = l_array[i];
                i = i + 1;
            } else {
                array[k] = r_array[j];
                j = j + 1;
            }
        }
        if (AlgorithmsUtils.needShowStep(array.length)) {
            log.debug("--------merge-{}, array:{}", 2, array);
        }
    }

    public void mergeSort(Integer[] array, int p, int r) {
        if (p < r) {
            int q = (p + r) / 2;
            mergeSort(array, p, q);
            mergeSort(array, q + 1, r);

            merge(array, p, q, r);
        }

    }

    public Integer[] sort(Integer[] array) {
        mergeSort(array, 1, array.length);
        return array;
    }

    public static void main(String[] args) {
        LogUtils.resetLogLevel(log, org.slf4j.event.Level.INFO);
        Integer[] originArray = null;
        Integer[] sortResult = null;
        AbstractArraySort sort = new MergeSort();
        StopWatch sw = DateUtil.createStopWatch();
        originArray = AlgorithmsUtils.generateRandomArray(AlgorithmsConstant.MAX_VALUE);
        sw.start();
        sortResult = sort.sort(originArray);
        sw.stop();

        AlgorithmsUtils.printSortedArray(sortResult);
        log.info("size:{},totalStep:{},cost time:{}", sortResult.length, sort.getTotalStep(), sw.getLastTaskTimeMillis());
        log.info(sw.prettyPrint());
    }
}
